Alibaba

Limit pamięci: 32 MB

Aby otworzyć Sezam, trzeba mieć komplet co najmniej żetonów złotych, — srebrnych i — miedzianych. Alibaba ma początkowo pewną liczbą żetonów każdego rodzaju i może je wymieniać u strażnika Sezamu według ściśle określonych reguł. Każda reguła jest postaci:

()

gdzie: oznaczają odpowiednio liczby żetonów złotych, srebrnych i miedzianych, jakie Alibaba musi dać strażnikowi, zaś — liczby żetonów złotych, srebrnych i miedzianych, które otrzyma w wyniku transakcji wymiany. Żetony otrzymane w wyniku transakcji można wymieniać w kolejnych transakcjach.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia zestawy danych, z których każdy zawiera:
  • liczby żetonów złotych, srebrnych i miedzianych znajdujących się początkowo w posiadaniu Alibaby,
  • opis kompletu żetonów otwierającego Sezam, oraz reguły transakcji;
• dla każdego zestawu danych stwierdza, czy istnieje skończony ciąg transakcji, który pozwoli Alibabie zgromadzić komplet żetonów otwierający Sezam i jeśli tak, znajduje i wypisuje na standardowe wyjście minimalną długość takiego ciągu, a w przeciwnym przypadku wypisuje odpowiedź NIE.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita dodatnia (). Jest to liczba zestawów danych. Dalej są zapisane kolejno zestawy danych. Każdy zestaw danych składa się z wielu wierszy.

W pierwszym wierszu są zapisane trzy liczby całkowite nieujemne . Są to liczby żetonów złotych, srebrnych i miedzianych, jakie na początku ma Alibaba. W drugim wierszu są kolejne trzy liczby całkowite . Są to liczby żetonów złotych, srebrnych i miedzianych, jakie trzeba mieć, aby otworzyć Sezam. W trzecim wierszu jest zapisana liczba reguł , gdzie .

W każdym z kolejnych wierszy jest zapisany ciąg sześciu liczb należących do zbioru . Każda taka szóstka liczb jest zapisem jednej reguły transakcji: .

Liczby w każdym wierszu są pooddzielane pojedynczymi odstępami.

Wyjście

W -tym wierszu standardowego wyjścia należy wypisać wynik dla -tego zestawu danych:

• jedną liczbę całkowitą nieujemną, tj. minimalną liczbę transakcji wymiany, jakich Alibaba musi dokonać, aby zgromadzić komplet żetonów otwierający Sezam,
• albo jedno słowo NIE.

Przykład

Dla danych wejściowych:

2
2 2 2
3 3 3
3
0 1 1 2 0 0
1 0 1 0 2 0
1 1 0 0 0 2
1 1 1
2 2 2
4
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 1 0 0
2 0 0 0 2 2

poprawną odpowiedzią jest:

NIE
9

Autor zadania: Piotr Chrząstowski-Wachtel.